Driven by increasing usage of a variety of network applications, such as those involving the Internet, computer networks are of increasing interest. FIG. 1A depicts a computer network 1 as coupled to the Internet 30. The computer network 1 includes gateways 12 and 25 as well as switches 10 and 14. The switches 10 and 14 are coupled to hosts 2, 4 and 6 and hosts 16 and 18, respectively. The switches 10 and 14 are also coupled to servers 7 and 8 and server 20, respectively.
The switches 10 and 14 are often used to couple portions of the network 1 together, as well as to couple different networks together. FIG. 1B depicts a high-level block diagram of a switch 10 which can be used in a computer network such as the network 1. The switch 10 includes a switch fabric 43 coupled with blades 47, 48 and 49. Each blade 47, 48 and 49 is generally a circuit board and includes at least a network processor 42 coupled with ports 44. Thus, the ports 44 are coupled with hosts and servers (not shown in FIG. 1B). The blades 47, 48 and 49 can provide traffic to the switch fabric 43 and accept traffic from the switch fabric 43. Thus, any host connected with one of the blades 47, 48 or 49 can communicate with another host connected to another blade 47, 48 or 49 or connected to the same blade. Although shown only in the switch 10, the network processor 42 may also be used in a router or other mechanism for transmitting packets.
In order to manage communications in a network, the network processor filter rules are used. In general, the network processor 42 determines how to enforce filter rules. A filter rule tests packets which are being transmitted via a network in order to provide a variety of services. A filter rule may test packets entering the network from an outside source to ensure that attempts to break into the network can be thwarted. For example, traffic from the Internet entering the network of the switch 10 may be tested in order to ensure that packets from unauthorized sources are denied entrance. Similarly, packets from one portion of a network may be prevented from accessing another portion of the network. For example, a packet from some of the hosts (not explicitly shown in FIG. 1B) may be prevented access to either a server (not shown in FIG. 1B) or another host. The fact that the host attempted to contact the server may also be recorded so that appropriate action can be taken by the owner of the network. Filter rules may also be used to transmit traffic based on the priorities of packets. For example, packets from a particular host may be transmitted because the packets have higher priority even when packets from other hosts may be dropped. Filter rules may also be used to ensure that new sessions are not permitted to be started when congestion is high even though traffic from established sessions is transmitted. Other functions could be achieved based on the filter rule.
Filter rules test a key in order to determine whether the filter rule will operate on a particular packet. The key that is typically used includes fields from the Internet Protocol (IP) header and the TCP/UDP header of the packet. These headers typically contain five fields (five tuple) of interest: the IP source address, the IP destination address, the TCP/UDP source port, the TCP/UDP destination port, and the protocol. These fields are typically thirty-two bits, thirty-two bits, sixteen bits, sixteen bits and eight bits, respectively. Thus, the part of IP header of interest is typically one hundred and four bits in length. Filter rules typically utilize these one hundred and four bits, and possible more bits, in order to perform their functions. For example, based on the source and destination addresses, the filter rule may determine whether a packet from a particular host is allowed to reach a particular destination address.
Furthermore, the key often contains additional bits. For example, a TCP SYN (start of session) packet, which starts a session, may need to be handled differently than a TCP packet for an existing session. The TCP header's SYN flag can be included in the key to distinguish between these two types of packets. When the network is congested, a filter rule may proactively drop the TCP SYN packet while allowing the TCP packets for existing sessions to be transmitted. These operations allow the network to continue to operate and help reduce congestion. In order to perform this function, however, the filter rule key must contain the TCP header's SYN flag in order to distinguish between these two types of packets.
Filter rules typically utilize one or more ranges of values to test one or more fields of a key. For example, if a key utilizes the five tuple described earlier, the criteria for the filter rule would typically include a range of values for one or more of these five fields. Range fields are typically expressed in terms of a lower and upper boundaries.
In general, in order to determine which rules from a set of filter rules to apply to a particular packet, the key for the packet is tested against the filter rules for the network 1. Exact comparisons are made between the rule and packet for non-range key fields. Fields in the key which are expressed in terms of ranges must be tested to determine if the packet's value for that field falls within the range specified by the rule.
Filter rules can interact based on the priority for the filter rule. Suppose that two filter rules are defined such that they intersect, where the first filter rule is an exception to the second filter rule. A packet matching the first filter rule would also match the second filter rule. A packet matching the second filter rule will not necessarily match the first filter rule. The second filter rule can be viewed as a default rule. In such a case, the first filter rule must be of higher priority than the second filter rule to ensure that when a packet matches both filter rules that the first filter rule dominates.
FIG. 2 depicts a high-level flow chart of a conventional method 50 for determining which, if any, filter rules to enforce for a particular packet. The method 50 is described more fully in co-pending U.S. patent application Ser. No. 09/312148 entitled “System and Method and Computer Program for Filtering Using Tree Structure” (RAL919990006US4) filed on Oct. 19, 1999 and assigned to the assignee of the present invention. Applicant hereby incorporates by reference the above-mentioned co-pending patent application. The method 50 is typically performed by the network processor 42. The possible filter rules which can match the key are narrowed to a set of remaining filter rules. This is done via step 52 which eliminates rules which cannot match the key. Step 52 can be accomplished using a decision tree. A decision tree contains nodes which perform a test, branches which indicate where in the decision tree to go based on the test, and leaves which correspond to some number of filter rules. At each node of the decision tree, a single bit of the key is tested. Based on the results of a test at a node, a different branch is taken. The branch can lead to another node or to a leaf. Each node thus excludes some of the filter rules from being enforced against the packet. The process of testing individual bits of the key is continued until a leaf in the decision tree is reached. The leaf includes one or more filter rules which cannot be distinguished by further testing of individual bits. If the leaf includes a single filter rule, then this filter rule may be enforced for the packet. However, if the leaf includes multiple filter rules, then it must be determined which, if any, of these remaining filter rules match the key.
It is determined which, if any, of the remaining filter rules match the key, typically by testing the entire key against each of the remaining filter rules, via step 54. Thus, step 54 uses brute force to determine whether any filter rule matches the key by testing (exact or range as appropriate) all bits of the key against the filter rules. Consequently, step 54 can determine precisely which filter rules, if any, match the key and are to be enforced against the packet.
Although the method 50 functions, one of ordinary skill in the art will readily recognize that the method 50 is time consuming. The remaining filter rules tested in step 54 may include a large number of filter rules. Step 54 tests all bits of the key against each of the remaining filter until a filter rule matching the key is found. Testing each bit of the key against a single filter rule requires a relatively large amount of time as compared to a single bit test carried out in step 52. In addition, the order in which the key is tested against the remaining filter rules in step 54 may result in the key being tested against the matching filter rule near the end set of the remaining filter rules. Thus, the key may frequently be tested against a large number of filter rules which do not match the key. The test of the key against each of these (non-matching) filter rules requires a relatively large amount of time, resulting in additional delays. Thus, even when step 52 is optimized to rapidly obtain the set of remaining filter rules, performing step 54 to identify the filter rule(s) that exactly match the key may result in delays.
Accordingly, what is needed is a system and method for more efficiently testing keys. The present invention addresses such a need.